Fibonacci prime

 ( Classes Of Prime Numbers ) 

A Fibonacci prime is a Fibonacci number that is prime number, a type of integer sequence prime.

The first Fibonacci primes are :

2, 3, 5, 13, 89, 233, 1597, 28657, 514229, 433494437, 2971215073, ....

---

Known Fibonacci primes It is not known whether there are Infinity many Fibonacci primes. With the indexing starting with , the first 37 indices n for which F _n is prime are :

n = 3, 4, 5, 7, 11, 13, 17, 23, 29, 43, 47, 83, 131, 137, 359, 431, 433, 449, 509, 569, 571, 2971, 4723, 5387, 9311, 9677, 14431, 25561, 30757, 35999, 37511, 50833, 81839, 104911, 130021, 148091, 201107.

(Note that the actual values F _n rapidly become very large, so, for practicality, only the indices are listed.)

In addition to these proven Fibonacci primes, several have been found:

n = 397379, 433781, 590041, 593689, 604711, 931517, 1049897, 1285607, 1636007, 1803059, 1968721, 2904353, 3244369, 3340367, 4740217, 6530879, 7789819, 10317107, 10367321. PRP Top Records, Search for : F(n). Retrieved 2018-04-05.

Except for the case n = 4, all Fibonacci primes have a prime index, because if a divisor b, then $F\_a$ also divides $F\_b$ (but not every prime index results in a Fibonacci prime). That is to say, the Fibonacci sequence is a divisibility sequence.

F _p is prime for 8 of the first 10 primes p; the exceptions are F₂ = 1 and F₁₉ = 4181 = 37 × 113. However, Fibonacci primes appear to become rarer as the index increases. F _p is prime for only 26 of the 1229 primes p smaller than 10,000.Sloane's , The number of prime factors in the Fibonacci numbers with prime index are:

0, 1, 1, 1, 1, 1, 1, 2, 1, 1, 2, 3, 2, 1, 1, 2, 2, 2, 3, 2, 2, 2, 1, 2, 4, 2, 3, 2, 2, 2, 2, 1, 1, 3, 4, 2, 4, 4, 2, 2, 3, 3, 2, 2, 4, 2, 4, 4, 2, 5, 3, 4, 3, 2, 3, 3, 4, 2, 2, 3, 4, 2, 4, 4, 4, 3, 2, 3, 5, 4, 2, 1, ...

, the largest known certain Fibonacci prime is F₂₀₁₁₀₇, with 42029 digits. It was proved prime by Maia Karpovich in September 2023. The largest known probable Fibonacci prime is F_10367321. It was found by Ryan Propper in July 2024. It was proved by Nick MacKinnon that the only Fibonacci numbers that are also are 3, 5, and 13.N. MacKinnon, Problem 10844, Amer. Math. Monthly 109, (2002), p. 78

---

Divisibility of Fibonacci numbers A prime $p$ divides $F\_\{p-1\}$ if and only if p is congruent to ±1 modulo 5, and p divides $F\_\{p+1\}$ if and only if it is congruent to ±2 modulo 5. (For p = 5, F₅ = 5 so 5 divides F₅)

Fibonacci numbers that have a prime index p do not share any common divisors greater than 1 with the preceding Fibonacci numbers, due to the identity:Paulo Ribenboim, My Numbers, My Friends, Springer-Verlag 2000

$\backslash gcd(F\_n,\; F\_m)\; =\; F\_\{\backslash gcd(n,m)\}.$

For , F_n divides F_m if and only if n divides m.Wells 1986, p.65

If we suppose that m is a prime number p, and n is less than p, then it is clear that F _p cannot share any common divisors with the preceding Fibonacci numbers.

$\backslash gcd(F\_p,\; F\_n)\; =\; F\_\{\backslash gcd(p,n)\}\; =\; F\_1\; =\; 1.$

This means that F_p will always have characteristic factors or be a prime characteristic factor itself. The number of distinct prime factors of each Fibonacci number can be put into simple terms.

• F _nk is a multiple of F _k for all values of n and k such that n ≥ 1 and k ≥ 1.The mathematical magic of Fibonacci numbers Factors of Fibonacci numbers It's safe to say that F_nk will have "at least" the same number of distinct prime factors as F_k. All F _p will have no factors of F _k, but "at least" one new characteristic prime from Carmichael's theorem.
• Carmichael's Theorem applies to all Fibonacci numbers except four special cases: $F\_1\; =F\_2\; =1,\; F\_6\; =\; 8$ and $F\_\{12\}\; =\; 144.$ If we look at the prime factors of a Fibonacci number, there will be at least one of them that has never before appeared as a factor in any earlier Fibonacci number. Let π_n be the number of distinct prime factors of F_n.

:If k | n then $\backslash pi\_n\; \backslash geqslant\; \backslash pi\_k\; +1$ except for $\backslash pi\_6\; =\; \backslash pi\_3\; =1.$

:If k = 1, and n is an odd prime, then 1 | p and $\backslash pi\_p\; \backslash geqslant\; \backslash pi\_1\; +1\; =\; 1.$

The first step in finding the characteristic quotient of any F_n is to divide out the prime factors of all earlier Fibonacci numbers F_k for which k | n.Jarden - Recurring sequences, Volume 1, Fibonacci quarterly, by Brother U. Alfred

The exact quotients left over are prime factors that have not yet appeared.

If p and q are both primes, then all factors of F_pq are characteristic, except for those of F_p and F_q.

$\backslash begin\{align\}$

\gcd (F_{pq}, F_q ) &= F_{\gcd(pq, q)} = F_q \\ \gcd (F_{pq}, F_p ) &= F_{\gcd(pq, p)} = F_p \end{align}

Therefore:

The number of distinct prime factors of the Fibonacci numbers with a prime index is directly relevant to the counting function.

---

Rank of apparition For a prime p, the smallest index u > 0 such that F_u is divisible by p is called the rank of apparition (sometimes called Fibonacci entry point) of p and denoted a( p). The rank of apparition a( p) is defined for every prime p. The rank of apparition divides the Pisano period π( p) and allows to determine all Fibonacci numbers divisible by p.

For the divisibility of Fibonacci numbers by powers of a prime, $p\; \backslash geqslant\; 3,\; n\; \backslash geqslant\; 2$ and $k\; \backslash geqslant\; 0$

$p^n\; \backslash mid\; F\_\{a(p)kp^\{n-1\}\}.$

In particular

$p^2\; \backslash mid\; F\_\{a(p)p\}.$

---

Wall–Sun–Sun primes A prime p ≠ 2, 5 is called a Fibonacci–Wieferich prime or a Wall–Sun–Sun prime if $p^2\; \backslash mid\; F\_q,$ where

$q\; =\; p\; -\; \backslash left(\backslash frac\backslash right)$

and $\backslash left(\backslash tfrac\backslash right)$ is the Legendre symbol:

It is known that for p ≠ 2, 5, a( p) is a divisor of:

For every prime p that is not a Wall–Sun–Sun prime, $a(p^2)\; =\; p\; a(p)$ as illustrated in the table below:

The existence of Wall–Sun–Sun primes is conjecture.

---

Fibonacci primitive part Because $F\_a\; |\; F\_\{ab\}$, we can divide any Fibonacci number $F\_n$ by the least common multiple of all $F\_d$ where $d\; |\; n$. The result is called the primitive part of $F\_n$. The primitive parts of the Fibonacci numbers are

1, 1, 2, 3, 5, 4, 13, 7, 17, 11, 89, 6, 233, 29, 61, 47, 1597, 19, 4181, 41, 421, 199, 28657, 46, 15005, 521, 5777, 281, 514229, 31, 1346269, 2207, 19801, 3571, 141961, 321, 24157817, 9349, 135721, 2161, 165580141, 211, 433494437, 13201, 109441, ...

Any primes that divide $F\_n$ and not any of the $F\_d$s are called primitive prime factors of $F\_n$. The product of the primitive prime factors of the Fibonacci numbers are

1, 1, 2, 3, 5, 1, 13, 7, 17, 11, 89, 1, 233, 29, 61, 47, 1597, 19, 4181, 41, 421, 199, 28657, 23, 3001, 521, 5777, 281, 514229, 31, 1346269, 2207, 19801, 3571, 141961, 107, 24157817, 9349, 135721, 2161, 165580141, 211, 433494437, 13201, 109441, 64079, 2971215073, 1103, 598364773, 15251, ...

The first case of more than one primitive prime factor is 4181 = 37 × 113 for $F\_\{19\}$.

The primitive part has a non-primitive prime factor in some cases. The ratio between the two above sequences is

1, 1, 1, 1, 1, 4, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 7, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 13, 1, 1, ....

The n for which $F\_n$ has exactly one primitive prime factor are

3, 4, 5, 7, 8, 9, 10, 11, 13, 14, 15, 16, 17, 18, 20, 21, 22, 23, 24, 25, 26, 28, 29, 30, 32, 33, 34, 35, 36, 38, 39, 40, 42, 43, 45, 47, 48, 51, 52, 54, 56, 60, 62, 63, 65, 66, 72, 74, 75, 76, 82, 83, 93, 94, 98, 105, 106, 108, 111, 112, 119, 121, 122, 123, 124, 125, 131, 132, 135, 136, 137, 140, 142, 144, 145, ...

For a prime p, p is in this sequence if and only if $F\_p$ is a Fibonacci prime, and 2 p is in this sequence if and only if $L\_p$ is a Lucas prime (where $L\_p$ is the $p$th Lucas sequence). Moreover, 2 ⁿ is in this sequence if and only if $L\_\{2^\{n-1\}\}$ is a Lucas prime.

The number of primitive prime factors of $F\_n$ are

0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 1, 1, 3, 1, 1, 1, 2, 1, 1, 2, 1, 2, 1, 1, 2, 2, 1, 1, 2, 1, 2, 1, 2, 2, 2, 1, 2, 1, 1, 2, 1, 1, 3, 2, 3, 2, 2, 1, 2, 1, 1, 1, 2, 2, 2, 2, 3, 1, 1, 2, 2, 2, 2, 3, 2, 2, 2, 2, 1, 1, 3, 2, 4, 1, 2, 2, 2, 2, 3, 2, 1, 1, 2, 1, 2, 2, 1, 1, 2, 2, 2, 2, 2, 3, 1, 2, 1, 1, 1, 1, 1, 2, 2, 2, ...

The least primitive prime factors of $F\_n$ are

1, 1, 2, 3, 5, 1, 13, 7, 17, 11, 89, 1, 233, 29, 61, 47, 1597, 19, 37, 41, 421, 199, 28657, 23, 3001, 521, 53, 281, 514229, 31, 557, 2207, 19801, 3571, 141961, 107, 73, 9349, 135721, 2161, 2789, 211, 433494437, 43, 109441, 139, 2971215073, 1103, 97, 101, ...

It is conjectured that all the prime factors of $F\_n$ are primitive when $n$ is a prime number.The mathematical magic of Fibonacci numbers Fibonacci Numbers and Primes

---

Fibonacci numbers in prime-like sequences Although it is not known whether there are infinitely many Fibonacci numbers which are prime, Giuseppe Melfi proved that there are infinitely many which are , a sequence which resembles the primes in some respects.

---

See also

• Lucas number

---

External links

• R. Knott Fibonacci primes
• Caldwell, Chris. Fibonacci number, Fibonacci prime, and Record Fibonacci primes at the Prime Pages
• Factorization of the first 300 Fibonacci numbers
• Factorization of Fibonacci and Lucas numbers
• Small parallel Haskell program to find probable Fibonacci primes at haskell.org

Post Comment